package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeLevelOrderTraversalII {
	 public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
	       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
	       
	       if (root != null){
	           Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>();
	           
	           TreeNode fake = new TreeNode(0);
	           
	           Queue<TreeNode> q = new LinkedList<TreeNode>();
	           q.offer(root);
	           q.offer(fake);
	           
	           ArrayList<Integer> lvl = new ArrayList<Integer>();
	           TreeNode c;
	           
	           while((c = q.poll()) != null){
	               if( c == fake){
	                   stack.add(lvl);
	                   lvl = new ArrayList<Integer>();
	                   if (q.peek() != null)
	                    q.offer(fake);
	               } else{
	                   lvl.add(c.val);
	                   if (c.left != null) q.offer(c.left);
	                   if (c.right != null) q.offer(c.right);
	               }
	           }
	           
	          while(!stack.empty()){
	              res.add(stack.pop());
	          }
	       }
	       
	       return res;
	        
	    }
	 
	 public ArrayList<ArrayList<Integer>> levelOrderBottom2(TreeNode root) {
	       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
	       
	       if (root != null){
	           TreeNode fake = new TreeNode(0);
	           
	           Queue<TreeNode> q = new LinkedList<TreeNode>();
	           q.offer(root);
	           q.offer(fake);
	           
	           ArrayList<Integer> lvl = new ArrayList<Integer>();
	           TreeNode c;
	           
	           while((c = q.poll()) != null){
	               if( c == fake){
	                   res.add(lvl);
	                   lvl = new ArrayList<Integer>();
	                   if (q.peek() != null)
	                    q.offer(fake);
	               } else{
	                   lvl.add(c.val);
	                   if (c.left != null) q.offer(c.left);
	                   if (c.right != null) q.offer(c.right);
	               }
	           }
	           
	           int h = 0, t = res.size()-1;
	           while (h<t){
	               ArrayList<Integer> tmp = res.get(h);
	               res.set(h, res.get(t));
	               res.set(t, tmp);
	               ++h;
	               --t;
	           }
	       }
	       
	       return res;
	    }
}
